{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #集水器"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #union-find #array #matrix"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #并查集 #数组 #矩阵"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: reservoir"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #集水器"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "字符串数组 `shape` 描述了一个二维平面中的矩阵形式的集水器，`shape[i][j]` 表示集水器的第 `i` 行 `j` 列为：\n",
    "- `'l'`表示向左倾斜的隔板（即从左上到右下）；\n",
    "- `'r'`表示向右倾斜的隔板（即从左下到右上）；\n",
    "- `'.'` 表示此位置没有隔板\n",
    "![image.png](https://pic.leetcode-cn.com/1664424667-wMnPja-image.png){:width=200px}\n",
    "\n",
    "已知当隔板构成存储容器可以存水，每个方格代表的蓄水量为 `2`。集水器初始浸泡在水中，除内部密闭空间外，所有位置均被水填满。\n",
    "现将其从水中竖直向上取出，请返回集水器最终的蓄水量。\n",
    "\n",
    "**注意：**\n",
    "- 隔板具有良好的透气性，因此空气可以穿过隔板，但水无法穿过\n",
    "\n",
    "**示例 1：**\n",
    "> 输入：\n",
    "> `shape = [\"....rl\",\"l.lr.r\",\".l..r.\",\"..lr..\"]`\n",
    ">\n",
    "> 输出：`18`\n",
    ">\n",
    "> 解释：如下图所示，由于空气会穿过隔板，因此红框区域没有水\n",
    "![image.png](https://pic.leetcode-cn.com/1664436239-eyYxeP-image.png){:width=\"280px\"}\n",
    "\n",
    "\n",
    "**示例 2：**\n",
    "> 输入：\n",
    "> `shape = [\".rlrlrlrl\",\"ll..rl..r\",\".llrrllrr\",\"..lr..lr.\"]`\n",
    "> 输出：`18`\n",
    ">\n",
    "> 解释：如图所示。由于红框右侧未闭合，因此多余的水会从该处流走。\n",
    "![image.png](https://pic.leetcode-cn.com/1664436082-SibVMv-image.png){:width=\"400px\"}\n",
    "\n",
    "\n",
    "**示例 3：**\n",
    "> 输入：\n",
    "> `shape = [\"rlrr\",\"llrl\",\"llr.\"]`\n",
    "> 输出：`6`\n",
    ">\n",
    "> 解释：如图所示。\n",
    "![image.png](https://pic.leetcode-cn.com/1664424855-dwpUHO-image.png){:width=\"230px\"}\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "**示例 4：**\n",
    "> 输入：\n",
    "> `shape = [\"...rl...\",\"..r..l..\",\".r.rl.l.\",\"r.r..l.l\",\"l.l..rl.\",\".l.lr.r.\",\"..l..r..\",\"...lr...\"]`\n",
    ">\n",
    "> 输出：`30`\n",
    ">\n",
    "> 解释：如下图所示。由于中间为内部密闭空间，无法蓄水。\n",
    "![image.png](https://pic.leetcode-cn.com/1664424894-mClEXh-image.png){:width=\"350px\"}\n",
    "\n",
    "\n",
    "**提示**：\n",
    "- `1 <= shape.length <= 50`\n",
    "- `1 <= shape[i].length <= 50`\n",
    "- `shape[i][j]` 仅为 `'l'`、`'r'` 或 `'.'`\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [kskhHQ](https://leetcode.cn/problems/kskhHQ/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [kskhHQ](https://leetcode.cn/problems/kskhHQ/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[\"....rl\",\"l.lr.r\",\".l..r.\",\"..lr..\"]', '[\".rlrlrlrl\",\"ll..rl..r\",\".llrrllrr\",\"..lr..lr.\"]', '[\"rlrr\",\"llrl\",\"llr.\"]', '[\"...rl...\",\"..r..l..\",\".r.rl.l.\",\"r.r..l.l\",\"l.l..rl.\",\".l.lr.r.\",\"..l..r..\",\"...lr...\"]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reservoir(self, shape: List[str]) -> int:\n",
    "        M = len(shape)\n",
    "        N = len(shape[0])\n",
    "        shape = [list(e) for e in shape]\n",
    "\n",
    "        # 'l' 表示向左倾斜的隔板（即从左上到右下）；\n",
    "        # 'r' 表示向右倾斜的隔板（即从左下到右上）；\n",
    "        # '.' 表示此位置没有隔板\n",
    "        # l分为两个lx，l1为左下角，l2为右上角\n",
    "        # r分为两个rx，r1为左上角，r2为右下角\n",
    "        shape = [[{c + \"1\": 0, c + \"2\": 0} if c != \".\" else {c: 0} for c in row] for row in shape]\n",
    "\n",
    "        def shape_print():\n",
    "            s = \"   \"\n",
    "            for n in range(N):\n",
    "                s += str(n % 10) * 2\n",
    "            print(s)\n",
    "\n",
    "            for m in range(M):\n",
    "                str1 = str2 = \"%02d \" % m\n",
    "\n",
    "                for n in range(N):\n",
    "                    v = shape[m][n]\n",
    "                    if \".\" in v:\n",
    "                        if v[\".\"]:\n",
    "                            str1 += \"--\"\n",
    "                            str2 += \"--\"\n",
    "                        else:\n",
    "                            str1 += \"  \"\n",
    "                            str2 += \"  \"\n",
    "                    elif \"l1\" in v:\n",
    "                        if not v[\"l1\"] and not v[\"l2\"]:\n",
    "                            str1 += \"  \"\n",
    "                            str2 += \"  \"\n",
    "                        elif v[\"l1\"] and v[\"l2\"]:\n",
    "                            str1 += \"\\\\-\"\n",
    "                            str2 += \"-\\\\\"\n",
    "                        elif v[\"l1\"]:\n",
    "                            str1 += \"\\\\ \"\n",
    "                            str2 += \"-\\\\\"\n",
    "                        else:\n",
    "                            str1 += \"\\\\-\"\n",
    "                            str2 += \" \\\\\"\n",
    "\n",
    "                    else:\n",
    "                        if not v[\"r1\"] and not v[\"r2\"]:\n",
    "                            str1 += \"  \"\n",
    "                            str2 += \"  \"\n",
    "                        elif v[\"r1\"] and v[\"r2\"]:\n",
    "                            str1 += \"-/\"\n",
    "                            str2 += \"/-\"\n",
    "                        elif v[\"r1\"]:\n",
    "                            str1 += \"-/\"\n",
    "                            str2 += \"/ \"\n",
    "                        else:\n",
    "                            str1 += \" /\"\n",
    "                            str2 += \"/-\"\n",
    "\n",
    "                print(str1)\n",
    "                print(str2)\n",
    "\n",
    "\n",
    "        def calc():\n",
    "            ret = 0\n",
    "            for row in shape:\n",
    "                for cell in row:\n",
    "                    for p, f in cell.items():\n",
    "                        if f:\n",
    "                            ret += 2 if p == \".\" else 1\n",
    "            return ret\n",
    "\n",
    "        # 第一步浸泡\n",
    "        # 浸泡出水，看每个位置有哪些出水方向\n",
    "        d_pos_fx_s = {\".\":  ((0, 1), (0, -1), (1, 0), (-1, 0)),\n",
    "                    \"l1\": ((0, -1), (1, 0)),\n",
    "                    \"l2\": ((0, 1), (-1, 0)),\n",
    "                    \"r1\": ((0, -1), (-1, 0)),\n",
    "                    \"r2\": ((0, 1), (1, 0))}\n",
    "\n",
    "        # 出水，看每个方向可以进到哪些位置\n",
    "        d_fx_pos_s = {(0, 1): {\".\", \"r1\", \"l1\"},\n",
    "                   (0, -1): {\".\", \"l2\", \"r2\"},\n",
    "                   (1, 0): {\".\", \"l2\", \"r1\"},\n",
    "                   (-1, 0): {\".\", \"l1\", \"r2\"}}\n",
    "\n",
    "        # 当前浸泡出水位置\n",
    "        # 浸泡\n",
    "        def soak(_m, _n, p):\n",
    "            dp = [(_m, _n, p)]\n",
    "\n",
    "            while dp:\n",
    "                _m, _n, p = dp.pop()\n",
    "                for fx in d_pos_fx_s[p]:\n",
    "                    m = _m + fx[0]\n",
    "                    if m < 0 or m >= M:\n",
    "                        continue\n",
    "\n",
    "                    n = _n + fx[1]\n",
    "                    if n < 0 or n >= N:\n",
    "                        continue\n",
    "\n",
    "                    ps = d_fx_pos_s[fx]\n",
    "                    for p, f in shape[m][n].items():\n",
    "                        if f == 0 and p in ps:\n",
    "                            dp.append((m, n, p))\n",
    "                            shape[m][n][p] = 1\n",
    "\n",
    "        # 从四周开始浸泡\n",
    "        for m in range(M):\n",
    "            soak(m, -1, \".\")\n",
    "            soak(m, N, \".\")\n",
    "\n",
    "        for n in range(N):\n",
    "            soak(-1, n, \".\")\n",
    "            soak(M, n, \".\")\n",
    "\n",
    "        # ppp(shape)\n",
    "\n",
    "        # 第二步提起排水\n",
    "        # 排水，看每个位置有哪些方向可向其排水\n",
    "        d_pos_fx_t = {\".\":  ((0, 1), (0, -1), (-1, 0)),\n",
    "                    \"l1\": ((0, -1),),\n",
    "                    \"l2\": ((0, 1), (-1, 0)),\n",
    "                    \"r1\": ((0, -1), (-1, 0)),\n",
    "                    \"r2\": ((0, 1),)}\n",
    "\n",
    "        # 排水，看每个方向可以排水的位置\n",
    "        d_fx_pos_t = {(0, 1): {\".\", \"l1\", \"r1\"},\n",
    "                    (0, -1): {\".\", \"l2\", \"r2\"},\n",
    "                    (-1, 0): {\".\", \"l1\", \"r2\"}}\n",
    "\n",
    "        def drain(m, n, p):\n",
    "            dp = [(m, n, p)]\n",
    "\n",
    "            while dp:\n",
    "                _m, _n, p = dp.pop()\n",
    "                for fx in d_pos_fx_t[p]:\n",
    "                    m = _m + fx[0]\n",
    "                    if m < 0 or m >= M:\n",
    "                        continue\n",
    "\n",
    "                    n = _n + fx[1]\n",
    "                    if n < 0 or n >= N:\n",
    "                        continue\n",
    "\n",
    "                    ps = d_fx_pos_t[fx]\n",
    "                    for p, f in shape[m][n].items():\n",
    "                        if p in ps and f == 1:\n",
    "                            shape[m][n][p] = 0\n",
    "                            dp.append((m, n, p))\n",
    "\n",
    "        # 从四周开始排水\n",
    "        for n in range(N):\n",
    "            drain(M, n, \".\")\n",
    "\n",
    "        for m in range(M):\n",
    "            drain(m, -1, \".\")\n",
    "            drain(m, N, \".\")\n",
    "\n",
    "        # 第三步，计算连通性\n",
    "        # 可上下的位置\n",
    "        l_pos_u = (\".\", \"l1\", \"r2\")\n",
    "        l_pos_d = (\".\", \"l2\", \"r1\")\n",
    "\n",
    "        for minm in range(M - 2, -1, -1):\n",
    "            done = set()\n",
    "\n",
    "            while 1:\n",
    "                dp = []\n",
    "\n",
    "                for n in range(N):\n",
    "                    for p, f in shape[minm][n].items():\n",
    "                        if f == 0 and p in l_pos_u:\n",
    "                            for p, f in shape[minm + 1][n].items():\n",
    "                                if f == 1 and p in l_pos_d and (minm + 1, n, p) not in done:\n",
    "                                    dp.append((minm + 1, n, p))\n",
    "                                    done.add((minm + 1, n, p))\n",
    "\n",
    "                if not dp:\n",
    "                    break\n",
    "\n",
    "                # 查找所有连通位置，实际上就是浸泡，但高度不小于minm\n",
    "                while dp:\n",
    "                    _m, _n, p = dp.pop()\n",
    "\n",
    "                    if _m == minm:\n",
    "                        shape[minm][_n][p] = 0\n",
    "                        drain(minm, _n, p)\n",
    "\n",
    "                    for fx in d_pos_fx_s[p]:\n",
    "                        m = _m + fx[0]\n",
    "                        if m < minm or m >= M:\n",
    "                            continue\n",
    "\n",
    "                        n = _n + fx[1]\n",
    "                        if n < 0 or n >= N:\n",
    "                            continue\n",
    "\n",
    "                        ps = d_fx_pos_s[fx]\n",
    "                        for p, f in shape[m][n].items():\n",
    "                            if f == 1 and p in ps and (m, n, p) not in done:\n",
    "                                dp.append((m, n, p))\n",
    "                                done.add((m, n, p))\n",
    "\n",
    "        ret = calc()\n",
    "        # shape_print()\n",
    "        return ret\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reservoir(self, shape: List[str]) -> int:\n",
    "        m,n = len(shape),len(shape[0])\n",
    "        pa = list(range(m*n*4+1))\n",
    "        we = [1] * (m*n*4+1)\n",
    "        def find(x):\n",
    "            if pa[x] != x:\n",
    "                pa[x] = find(pa[x])\n",
    "            return pa[x]\n",
    "        def union(i,j):\n",
    "            x,y = map(find,[i,j])\n",
    "            if x==y: return\n",
    "            if we[x]<we[y]: x,y = y,x\n",
    "            pa[y] = x\n",
    "            we[x] += we[y]\n",
    "        mat = [[[False]*4 for _ in range(n)] for _ in range(m)]\n",
    "        for i in range(m):\n",
    "            union(m*n*4,i*n*4+1)\n",
    "            union(m*n*4,(i*n+n-1)*4+3)\n",
    "            for j in range(n-1):\n",
    "                union((i*n+j)*4+3,(i*n+j+1)*4+1)\n",
    "        for j in range(n):\n",
    "            union(((m-1)*n+j)*4+2,4*m*n)\n",
    "        for i in range(m-1,-1,-1):\n",
    "            for j in range(n):\n",
    "                if i < m-1: union((i*n+j)*4+2,((i+1)*n+j)*4)\n",
    "                loc = i*n+j\n",
    "                if shape[i][j] in 'l.':\n",
    "                    union(loc*4,loc*4+3)\n",
    "                    union(loc*4+1,loc*4+2)\n",
    "                if shape[i][j] in 'r.':\n",
    "                    union(loc*4,loc*4+1)\n",
    "                    union(loc*4+2,loc*4+3)\n",
    "            for j in range(n):\n",
    "                for k in range(4):\n",
    "                    if find((i*n+j)*4+k) != find(m*n*4): mat[i][j][k] = True\n",
    "        for j in range(n): union(j*4,m*n*4)\n",
    "        ans = 0\n",
    "        zero = find(m*n*4)\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                for k in range(4):\n",
    "                    if mat[i][j][k] and find((i*n+j)*4+k) == zero: ans += 1\n",
    "                    if mat[i][j][k] and not find((i*n+j)*4+k) == zero:\n",
    "                        mat[i][j][k] = False\n",
    "        # for l in mat:\n",
    "        #     for a in l:\n",
    "        #         for b in a: print('1' if b else '0',end = '')\n",
    "        #         print(' ',end='')\n",
    "        #     print()\n",
    "        return ans//2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reservoir(self, shape: List[str]) -> int:\n",
    "        m,n = len(shape),len(shape[0])\n",
    "        pa = list(range(m*n*4))\n",
    "        we = [1] * (m*n*4)\n",
    "        def find(x):\n",
    "            if pa[x] != x:\n",
    "                pa[x] = find(pa[x])\n",
    "            return pa[x]\n",
    "        def union(i,j):\n",
    "            x,y = map(find,[i,j])\n",
    "            if x==y: return\n",
    "            if we[x]<we[y]: x,y = y,x\n",
    "            pa[y] = x\n",
    "            we[x] += we[y]\n",
    "        mat = [[[False]*4 for _ in range(n)] for _ in range(m)]\n",
    "        for i in range(m):\n",
    "            union(1,i*n*4+1)\n",
    "            union(1,(i*n+n-1)*4+3)\n",
    "            for j in range(n-1):\n",
    "                union((i*n+j)*4+3,(i*n+j+1)*4+1)\n",
    "        for j in range(n):\n",
    "            union(((m-1)*n+j)*4+2,1)\n",
    "        for i in range(m-1,-1,-1):\n",
    "            for j in range(n):\n",
    "                if i < m-1: union((i*n+j)*4+2,((i+1)*n+j)*4)\n",
    "                loc = i*n+j\n",
    "                if shape[i][j] in 'l.':\n",
    "                    union(loc*4,loc*4+3)\n",
    "                    union(loc*4+1,loc*4+2)\n",
    "                if shape[i][j] in 'r.':\n",
    "                    union(loc*4,loc*4+1)\n",
    "                    union(loc*4+2,loc*4+3)\n",
    "            for j in range(n):\n",
    "                for k in range(4):\n",
    "                    if find((i*n+j)*4+k) != find(1): mat[i][j][k] = True\n",
    "        for j in range(n): union(j*4,1)\n",
    "        ans = 0\n",
    "        zero = find(1)\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                for k in range(4):\n",
    "                    if mat[i][j][k] and find((i*n+j)*4+k) == zero: ans += 1\n",
    "                    # if mat[i][j][k] and not find((i*n+j)*4+k) == zero:\n",
    "                    #     mat[i][j][k] = False\n",
    "        # for l in mat:\n",
    "        #     for a in l:\n",
    "        #         for b in a: print('1' if b else '0',end = '')\n",
    "        #         print(' ',end='')\n",
    "        #     print()\n",
    "        return ans//2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reservoir(self, shape: List[str]) -> int:\n",
    "        n, m = len(shape), len(shape[0])\n",
    "        # 每个格子分成四个区域（上下左右），标上序号，方便用并查集连通\n",
    "        # 假设左右下还有一圈格子，直接连到超级汇点 0\n",
    "        u = [[0] * (m + 2) for _ in range(n + 1)]\n",
    "        d = [[0] * (m + 2) for _ in range(n + 1)]\n",
    "        l = [[0] * (m + 2) for _ in range(n + 1)]\n",
    "        r = [[0] * (m + 2) for _ in range(n + 1)]\n",
    "        c = 1\n",
    "        for i in range(n):\n",
    "            for j in range(1, m + 1):  # 假设格子的列号从 1 开始，这样方便表示左右边界\n",
    "                u[i][j] = c; c += 1\n",
    "                d[i][j] = c; c += 1\n",
    "                l[i][j] = c; c += 1\n",
    "                r[i][j] = c; c += 1\n",
    "\n",
    "        # 并查集模板\n",
    "        fa = list(range(c))\n",
    "        def find(x: int) -> int:\n",
    "            if fa[x] != x:\n",
    "                fa[x] = find(fa[x])\n",
    "            return fa[x]\n",
    "        def merge(x: int, y: int):\n",
    "            fa[find(x)] = find(y)\n",
    "\n",
    "        ok = [False] * c  # 能否容纳水\n",
    "        # 倒着判断每一行，寻找可能有水的区域\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            for j in range(m + 1):\n",
    "                merge(r[i][j], l[i][j + 1])  # 连通左右\n",
    "            for j, type in enumerate(shape[i], 1):\n",
    "                merge(d[i][j], u[i + 1][j])  # 连通下\n",
    "                # 根据格子的类型连接格子内部四个区域\n",
    "                if type == '.':\n",
    "                    merge(l[i][j], u[i][j])\n",
    "                    merge(l[i][j], d[i][j])\n",
    "                    merge(l[i][j], r[i][j])\n",
    "                elif type == 'l':\n",
    "                    merge(l[i][j], d[i][j])\n",
    "                    merge(r[i][j], u[i][j])\n",
    "                else:\n",
    "                    merge(l[i][j], u[i][j])\n",
    "                    merge(r[i][j], d[i][j])\n",
    "            for j in range(1, m + 1):\n",
    "                # 在没有连接第 i-1 行的情况下，无法到达左右下边界 => 能容纳水\n",
    "                ok[l[i][j]] = find(l[i][j]) != find(0)\n",
    "                ok[r[i][j]] = find(r[i][j]) != find(0)\n",
    "                ok[u[i][j]] = find(u[i][j]) != find(0)\n",
    "                ok[d[i][j]] = find(d[i][j]) != find(0)\n",
    "\n",
    "        # 第一行连上超级汇点，方便后面统一判断是否在闭合区域里面\n",
    "        for j in range(1, m + 1):\n",
    "            merge(u[0][j], 0)\n",
    "\n",
    "        ans = 0\n",
    "        for i, b in enumerate(ok):\n",
    "            if b and find(i) == find(0):  # 能容纳水，且不在闭合区域里面\n",
    "                ans += 1\n",
    "        return ans // 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def reservoir(self, shape: List[str]) -> int:\n",
    "        n, m = len(shape), len(shape[0])\n",
    "        u = [[0] * (m + 2) for _ in range(n + 1)]\n",
    "        d = [[0] * (m + 2) for _ in range(n + 1)]\n",
    "        l = [[0] * (m + 2) for _ in range(n + 1)]\n",
    "        r = [[0] * (m + 2) for _ in range(n + 1)]\n",
    "        c = 1\n",
    "        for i in range(n):\n",
    "            for j in range(1, m + 1):\n",
    "                u[i][j] = c; c += 1\n",
    "                d[i][j] = c; c += 1\n",
    "                l[i][j] = c; c += 1\n",
    "                r[i][j] = c; c += 1\n",
    "\n",
    "        fa = list(range(c))\n",
    "        def find(x: int) -> int:\n",
    "            if fa[x] != x:\n",
    "                fa[x] = find(fa[x])\n",
    "            return fa[x]\n",
    "        def merge(x: int, y: int):\n",
    "            fa[find(x)] = find(y)\n",
    "\n",
    "        ok = [False] * c\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            for j in range(m + 1):\n",
    "                merge(r[i][j], l[i][j + 1])\n",
    "            for j, type in enumerate(shape[i], 1):\n",
    "                merge(d[i][j], u[i + 1][j])\n",
    "                if type == '.':\n",
    "                    merge(l[i][j], u[i][j])\n",
    "                    merge(l[i][j], d[i][j])\n",
    "                    merge(l[i][j], r[i][j])\n",
    "                elif type == 'l':\n",
    "                    merge(l[i][j], d[i][j])\n",
    "                    merge(r[i][j], u[i][j])\n",
    "                else:\n",
    "                    merge(l[i][j], u[i][j])\n",
    "                    merge(r[i][j], d[i][j])\n",
    "            for j in range(1, m + 1):\n",
    "                ok[l[i][j]] = find(l[i][j]) != find(0)\n",
    "                ok[r[i][j]] = find(r[i][j]) != find(0)\n",
    "                ok[u[i][j]] = find(u[i][j]) != find(0)\n",
    "                ok[d[i][j]] = find(d[i][j]) != find(0)\n",
    "\n",
    "        for j in range(1, m + 1):\n",
    "            merge(u[0][j], 0)\n",
    "\n",
    "        ans = 0\n",
    "        for i, b in enumerate(ok):\n",
    "            if b and find(i) == find(0):\n",
    "                ans += 1\n",
    "        return ans // 2\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reservoir(self, shape: List[str]) -> int:\n",
    "        n, m = len(shape), len(shape[0])\n",
    "        # 每个格子分成四个区域（上下左右），标上序号，方便用并查集连通\n",
    "        # 假设左右下还有一圈格子，直接连到超级汇点 0\n",
    "        u = [[0] * (m + 2) for _ in range(n + 1)]\n",
    "        d = [[0] * (m + 2) for _ in range(n + 1)]\n",
    "        l = [[0] * (m + 2) for _ in range(n + 1)]\n",
    "        r = [[0] * (m + 2) for _ in range(n + 1)]\n",
    "        c = 1\n",
    "        for i in range(n):\n",
    "            for j in range(1, m + 1):  # 假设格子的列号从 1 开始，这样方便表示左右边界\n",
    "                u[i][j] = c; c += 1\n",
    "                d[i][j] = c; c += 1\n",
    "                l[i][j] = c; c += 1\n",
    "                r[i][j] = c; c += 1\n",
    "\n",
    "        # 并查集模板\n",
    "        fa = list(range(c))\n",
    "        def find(x: int) -> int:\n",
    "            if fa[x] != x:\n",
    "                fa[x] = find(fa[x])\n",
    "            return fa[x]\n",
    "        def merge(x: int, y: int):\n",
    "            fa[find(x)] = find(y)\n",
    "\n",
    "        ok = [False] * c  # 能否容纳水\n",
    "        # 倒着判断每一行，寻找可能有水的区域\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            for j in range(m + 1):\n",
    "                merge(r[i][j], l[i][j + 1])  # 连通左右\n",
    "            for j, type in enumerate(shape[i], 1):\n",
    "                merge(d[i][j], u[i + 1][j])  # 连通下\n",
    "                # 根据格子的类型连接格子内部四个区域\n",
    "                if type == '.':\n",
    "                    merge(l[i][j], u[i][j])\n",
    "                    merge(l[i][j], d[i][j])\n",
    "                    merge(l[i][j], r[i][j])\n",
    "                elif type == 'l':\n",
    "                    merge(l[i][j], d[i][j])\n",
    "                    merge(r[i][j], u[i][j])\n",
    "                else:\n",
    "                    merge(l[i][j], u[i][j])\n",
    "                    merge(r[i][j], d[i][j])\n",
    "            for j in range(1, m + 1):\n",
    "                # 在没有连接第 i-1 行的情况下，无法到达左右下边界 => 能容纳水\n",
    "                ok[l[i][j]] = find(l[i][j]) != find(0)\n",
    "                ok[r[i][j]] = find(r[i][j]) != find(0)\n",
    "                ok[u[i][j]] = find(u[i][j]) != find(0)\n",
    "                ok[d[i][j]] = find(d[i][j]) != find(0)\n",
    "\n",
    "        # 第一行连上超级汇点，方便后面统一判断是否在闭合区域里面\n",
    "        for j in range(1, m + 1):\n",
    "            merge(u[0][j], 0)\n",
    "\n",
    "        ans = 0\n",
    "        for i, b in enumerate(ok):\n",
    "            if b and find(i) == find(0):  # 能容纳水，且不在闭合区域里面\n",
    "                ans += 1\n",
    "        return ans // 2\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reservoir(self, shape: List[str]) -> int:\n",
    "        n, m = len(shape), len(shape[0])\n",
    "        # 每个格子分成四个区域（上下左右），标上序号，方便用并查集连通\n",
    "        # 假设左右下还有一圈格子，直接连到超级汇点 0\n",
    "        u = [[0] * (m + 2) for _ in range(n + 1)]\n",
    "        d = [[0] * (m + 2) for _ in range(n + 1)]\n",
    "        l = [[0] * (m + 2) for _ in range(n + 1)]\n",
    "        r = [[0] * (m + 2) for _ in range(n + 1)]\n",
    "        c = 1\n",
    "        for i in range(n):\n",
    "            for j in range(1, m + 1):  # 假设格子的列号从 1 开始，这样方便表示左右边界\n",
    "                u[i][j] = c; c += 1\n",
    "                d[i][j] = c; c += 1\n",
    "                l[i][j] = c; c += 1\n",
    "                r[i][j] = c; c += 1\n",
    "\n",
    "        # 并查集模板\n",
    "        fa = list(range(c))\n",
    "        def find(x: int) -> int:\n",
    "            if fa[x] != x:\n",
    "                fa[x] = find(fa[x])\n",
    "            return fa[x]\n",
    "        def merge(x: int, y: int):\n",
    "            fa[find(x)] = find(y)\n",
    "\n",
    "        ok = [False] * c  # 能否容纳水\n",
    "        # 倒着判断每一行，寻找可能有水的区域\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            for j in range(m + 1):\n",
    "                merge(r[i][j], l[i][j + 1])  # 连通左右\n",
    "            for j, type in enumerate(shape[i], 1):\n",
    "                merge(d[i][j], u[i + 1][j])  # 连通下\n",
    "                # 根据格子的类型连接格子内部四个区域\n",
    "                if type == '.':\n",
    "                    merge(l[i][j], u[i][j])\n",
    "                    merge(l[i][j], d[i][j])\n",
    "                    merge(l[i][j], r[i][j])\n",
    "                elif type == 'l':\n",
    "                    merge(l[i][j], d[i][j])\n",
    "                    merge(r[i][j], u[i][j])\n",
    "                else:\n",
    "                    merge(l[i][j], u[i][j])\n",
    "                    merge(r[i][j], d[i][j])\n",
    "            for j in range(1, m + 1):\n",
    "                # 在没有连接第 i-1 行的情况下，无法到达左右下边界 => 能容纳水\n",
    "                ok[l[i][j]] = find(l[i][j]) != find(0)\n",
    "                ok[r[i][j]] = find(r[i][j]) != find(0)\n",
    "                ok[u[i][j]] = find(u[i][j]) != find(0)\n",
    "                ok[d[i][j]] = find(d[i][j]) != find(0)\n",
    "\n",
    "        # 第一行连上超级汇点，方便后面统一判断是否在闭合区域里面\n",
    "        for j in range(1, m + 1):\n",
    "            merge(u[0][j], 0)\n",
    "\n",
    "        ans = 0\n",
    "        for i, b in enumerate(ok):\n",
    "            if b and find(i) == find(0):  # 能容纳水，且不在闭合区域里面\n",
    "                ans += 1\n",
    "        return ans // 2\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reservoir(self, shape: List[str]) -> int:\n",
    "        n, m = len(shape), len(shape[0])\n",
    "        # 每个格子分成四个区域（上下左右），标上序号，方便用并查集连通\n",
    "        # 假设左右下还有一圈格子，直接连到超级汇点 0\n",
    "        u = [[0] * (m + 2) for _ in range(n + 1)]\n",
    "        d = [[0] * (m + 2) for _ in range(n + 1)]\n",
    "        l = [[0] * (m + 2) for _ in range(n + 1)]\n",
    "        r = [[0] * (m + 2) for _ in range(n + 1)]\n",
    "        c = 1\n",
    "        for i in range(n):\n",
    "            for j in range(1, m + 1):  # 假设格子的列号从 1 开始，这样方便表示左右边界\n",
    "                u[i][j] = c; c += 1\n",
    "                d[i][j] = c; c += 1\n",
    "                l[i][j] = c; c += 1\n",
    "                r[i][j] = c; c += 1\n",
    "\n",
    "        # 并查集模板\n",
    "        fa = list(range(c))\n",
    "        def find(x: int) -> int:\n",
    "            if fa[x] != x:\n",
    "                fa[x] = find(fa[x])\n",
    "            return fa[x]\n",
    "        def merge(x: int, y: int):\n",
    "            fa[find(x)] = find(y)\n",
    "\n",
    "        ok = [False] * c  # 能否容纳水\n",
    "        # 倒着判断每一行，寻找可能有水的区域\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            for j in range(m + 1):\n",
    "                merge(r[i][j], l[i][j + 1])  # 连通左右\n",
    "            for j, type in enumerate(shape[i], 1):\n",
    "                merge(d[i][j], u[i + 1][j])  # 连通下\n",
    "                # 根据格子的类型连接格子内部四个区域\n",
    "                if type == '.':\n",
    "                    merge(l[i][j], u[i][j])\n",
    "                    merge(l[i][j], d[i][j])\n",
    "                    merge(l[i][j], r[i][j])\n",
    "                elif type == 'l':\n",
    "                    merge(l[i][j], d[i][j])\n",
    "                    merge(r[i][j], u[i][j])\n",
    "                else:\n",
    "                    merge(l[i][j], u[i][j])\n",
    "                    merge(r[i][j], d[i][j])\n",
    "            for j in range(1, m + 1):\n",
    "                # 在没有连接第 i-1 行的情况下，无法到达左右下边界 => 能容纳水\n",
    "                ok[l[i][j]] = find(l[i][j]) != find(0)\n",
    "                ok[r[i][j]] = find(r[i][j]) != find(0)\n",
    "                ok[u[i][j]] = find(u[i][j]) != find(0)\n",
    "                ok[d[i][j]] = find(d[i][j]) != find(0)\n",
    "\n",
    "        # 第一行连上超级汇点，方便后面统一判断是否在闭合区域里面\n",
    "        for j in range(1, m + 1):\n",
    "            merge(u[0][j], 0)\n",
    "\n",
    "        ans = 0\n",
    "        for i, b in enumerate(ok):\n",
    "            if b and find(i) == find(0):  # 能容纳水，且不在闭合区域里面\n",
    "                ans += 1\n",
    "        return ans // 2\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reservoir(self, shape: List[str]) -> int:\n",
    "        n, m = len(shape), len(shape[0])\n",
    "        # 每个格子分成四个区域（上下左右），标上序号，方便用并查集连通\n",
    "        # 假设左右下还有一圈格子，直接连到超级汇点 0\n",
    "        u = [[0] * (m + 2) for _ in range(n + 1)]\n",
    "        d = [[0] * (m + 2) for _ in range(n + 1)]\n",
    "        l = [[0] * (m + 2) for _ in range(n + 1)]\n",
    "        r = [[0] * (m + 2) for _ in range(n + 1)]\n",
    "        c = 1\n",
    "        for i in range(n):\n",
    "            for j in range(1, m + 1):  # 假设格子的列号从 1 开始，这样方便表示左右边界\n",
    "                u[i][j] = c; c += 1\n",
    "                d[i][j] = c; c += 1\n",
    "                l[i][j] = c; c += 1\n",
    "                r[i][j] = c; c += 1\n",
    "\n",
    "        # 并查集模板\n",
    "        fa = list(range(c))\n",
    "        def find(x: int) -> int:\n",
    "            if fa[x] != x:\n",
    "                fa[x] = find(fa[x])\n",
    "            return fa[x]\n",
    "        def merge(x: int, y: int):\n",
    "            fa[find(x)] = find(y)\n",
    "\n",
    "        ok = [False] * c  # 能否容纳水\n",
    "        # 倒着判断每一行，寻找可能有水的区域\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            for j in range(m + 1):\n",
    "                merge(r[i][j], l[i][j + 1])  # 连通左右\n",
    "            for j, type in enumerate(shape[i], 1):\n",
    "                merge(d[i][j], u[i + 1][j])  # 连通下\n",
    "                # 根据格子的类型连接格子内部四个区域\n",
    "                if type == '.':\n",
    "                    merge(l[i][j], u[i][j])\n",
    "                    merge(l[i][j], d[i][j])\n",
    "                    merge(l[i][j], r[i][j])\n",
    "                elif type == 'l':\n",
    "                    merge(l[i][j], d[i][j])\n",
    "                    merge(r[i][j], u[i][j])\n",
    "                else:\n",
    "                    merge(l[i][j], u[i][j])\n",
    "                    merge(r[i][j], d[i][j])\n",
    "            for j in range(1, m + 1):\n",
    "                # 在没有连接第 i-1 行的情况下，无法到达左右下边界 => 能容纳水\n",
    "                ok[l[i][j]] = find(l[i][j]) != find(0)\n",
    "                ok[r[i][j]] = find(r[i][j]) != find(0)\n",
    "                ok[u[i][j]] = find(u[i][j]) != find(0)\n",
    "                ok[d[i][j]] = find(d[i][j]) != find(0)\n",
    "\n",
    "        # 第一行连上超级汇点，方便后面统一判断是否在闭合区域里面\n",
    "        for j in range(1, m + 1):\n",
    "            merge(u[0][j], 0)\n",
    "\n",
    "        ans = 0\n",
    "        for i, b in enumerate(ok):\n",
    "            if b and find(i) == find(0):  # 能容纳水，且不在闭合区域里面\n",
    "                ans += 1\n",
    "        return ans // 2\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
